Collaborative filtering is utilized as a tool to analyze users' behavior in a social network. The result of the analysis can be used to predict users' behavior (e.g., interests), so as to enable the social network to provide item recommendations (e.g., an item that a user may be interested in, such as a game, a movie, an article, etc.) for its users. Collaborative filtering analysis usually requires a significant amount of computing resources (especially for a social network having a large number of users). Therefore computing efficiency is extremely critical for a social network to provide a timely item-recommendation service to its users.
A directed graph is an abstract data structure that is often used by social networks to represent relationships among various users and items. A typical directed graph is “bipartite” and constituted by more than one node (or vertex) and at least one edge (e.g., a line between nodes). Traditionally, users and items are characterized as “nodes” in a directed graph and their relationships (e.g., a user “likes” a picture) are treated as “edges” in the directed graph. However, the traditional approach can consume a significant amount of computing resources when a large number of computations are involved, such as collaborative filtering analyses or computations for popular items (e.g., items with million users connected thereto). During peak hours (e.g., with high network traffic), high demands of computing resources caused by these analyses can result in system failures, malfunctions, and/or suspension of online services.